package com.jlhlyby.tree;

import java.util.Stack;

/**
 * 之字形（也叫蛇形）打印二叉树
 */
public class SnakePrintTree {
    public static void main(String[] args) {
        printTree(mockTree());
    }

    public static TreeNode mockTree() {
        TreeNode root = new TreeNode(1);
        TreeNode root2 = new TreeNode(2);
        TreeNode root3 = new TreeNode(3);
        TreeNode root4 = new TreeNode(4);
        TreeNode root5 = new TreeNode(5);
        TreeNode root6 = new TreeNode(6);
        TreeNode root7 = new TreeNode(7);
        root.left = root2;
        root.right = root3;
        root2.left = root7;
        root2.right = root6;
        root3.left = root5;
        root3.right = root4;
        System.out.println();
        return root;
    }

    public static void printTree(TreeNode root) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.add(root);
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            TreeNode node = null;
            while (!stack1.isEmpty()) {
                node = stack1.pop();
                System.out.println(node.val);
                if (node.right != null){
                    stack2.add(node.right);
                }
                if (node.left != null){
                    stack2.add(node.left);
                }

            }
            while (!stack2.isEmpty()) {
                node = stack2.pop();
                System.out.println(node.val);
                if (node.left != null){
                    stack1.add(node.left);
                }
                if (node.right != null){
                    stack1.add(node.right);
                }


            }
        }
    }

}
